package com.lw.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 403. 青蛙过河
 *
 * @Author liw
 * @Date 2021/4/29 9:18
 * @Version 1.0
 */
public class CanCross {

    public static void main(String[] args) {
        CanCross test = new CanCross();
        int[] arr = {0, 1, 3, 5, 6, 8, 12, 17};
        boolean b = test.canCross(arr);
        System.out.println(b);
    }


    public boolean canCross(int[] stones) {
        int l = stones.length;
        if (stones[1] != 1) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < l; i++) {
            map.put(stones[i], i);
        }
        boolean[][] arr = new boolean[l][l];
        arr[0][1] = true;
        for (int i = 0; i < l; i++) {
            for (int j = i; j < l; j++) {
                if (arr[i][j]) {
                    int value = stones[j] - stones[i] + stones[j];
                    Integer index = map.get(value - 1);
                    if (index != null) {
                        arr[j][index] = true;
                    }
                    index = map.get(value);
                    if (index != null) {
                        arr[j][index] = true;
                    }
                    index = map.get(value + 1);
                    if (index != null) {
                        arr[j][index] = true;
                    }
                }
            }
        }
        for (int j = 0; j < l; j++) {
            if (arr[j][l - 1]) {
                return true;
            }
        }
        return false;
    }


}
